import random
from typing import *


class Solution:
    def beautifulSubsets(self, nums: List[int], k: int) -> int:
        n = len(nums)
        dp = [0] * (1<<n)
        dp[0] = 1
        for i,v in enumerate(nums):
            for j in range(1<<i):
                if dp[j] !=0:
                    f = True
                    for t in range(i):
                        if (1<<t) & j !=0:
                            if abs(v - nums[t]) == k:
                                f = False
                                break
                    if f:
                        dp[1<<i | j] = dp[j]
        return sum(dp) - 1



# ls = []
# for i in range(20):
#     k = 1<<i
#     k *= (i + 1)
#     ls.append(k)

case = []
for _ in range(20):
    case.append(random.randint(1,1000))
print(case)


class Solution:
    def beautifulSubsets(self, nums: List[int], k: int) -> int:
        n = len(nums)
        dp = [0] * (1<<n)
        dp[0] = 1
        e = [0] * n
        ans = 0
        for i in range(n):
            for j in range(i):
                if abs(nums[i] - nums[j]) == k:
                    e[i]|=1<<j
        for i in range(n):
            for j in range(1<<i):
                if e[i] & j == 0:
                    dp[1<<i | j] = dp[j]
                    ans+=dp[j]
        return ans